package editor.cn;

import javax.swing.tree.TreeNode;
import java.util.LinkedList;
import java.util.Queue;

class Solution337{
    public static void main(String[] args) {
        Solution solution = new Solution337().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

  //Definition for a binary tree node.
  class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
 }

    class Solution {
        public int rob(TreeNode root) {
            int[] res = dfs(root);
            return Math.max(res[0], res[1]); // 根节点选或不选的最大值
        }

        private int[] dfs(TreeNode node) {
            if (node == null) { // 递归边界
                return new int[]{0, 0}; // 没有节点，怎么选都是 0
            }
            int[] left = dfs(node.left); // 递归左子树
            int[] right = dfs(node.right); // 递归右子树
            int rob = left[1] + right[1] + node.val; // 选
            int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]); // 不选
            return new int[]{rob, notRob};
        }
    }
}












